package week3;

import base.TreeNode;

/**
 *
 *
 * 98. 验证二叉搜索树
 * https://leetcode-cn.com/problems/validate-binary-search-tree/
 *
 *
 * 执行结果：  通过  显示详情
 *
 * 添加备注
 * 执行用时：0 ms, 在所有 Java 提交中击败了100.00% 的用户
 * 内存消耗：38 MB, 在所有 Java 提交中击败了70.30% 的用户
 *
 */
public class Week3ValidateBinarySearchTree {

    public boolean isValidBST(TreeNode root) {
        boolean valid = isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
        return valid;
    }

    /**
     *
     * @param node
     * @param lower (int 类型无法通过)
     * @param upper (int 类型无法通过)
     * @return
     */
    public boolean isValidBST(TreeNode node, long lower, long upper) {
        if(node == null) {
            // 空树 有效
            return true;
        }
        if(node.val <= lower || node.val >= upper) {
            // 当前节点 小于等于最小值 或者 大于 最大值 则无效
            return false;
        }
        // 递归校验
        boolean valid = isValidBST(node.left, lower, node.val) && isValidBST(node.right, node.val, upper);
        return valid;
    }

}
